package com.tuling.code;

public class MegeSort2 {

    public static int process(int [] arry,int left,int right){
        if(left == right){
            return arry[left];
        }

        int mid  = left + ((right - left)>>1);

        return process(arry,left,mid)+ process(arry,mid+1,right)+
            merge(arry,left,mid,right);
    }
    //最小和问题：以右组视角，左边有多少个数比当前数小；  相当于以左组视角看有多少个数比当前数大
    //站在左足视角，拷贝左组的时候 跨组找出右组比当前大的数的个数 right-p2
    private static int merge(int[] arry, int left, int mid, int right) {
        int[] help = new int[right - left +1];

        //定义三个变量
        int i =0;
        int p1 = left;
        int p2 = mid +1;
        int res = 0;
        while (p1<=mid && p2 <= right){
            res += arry[p1] < arry[p2] ? arry[p1] *(right - p2 +1):0;
            help[i++] = arry[p1] <arry[p2] ? arry[p1++] :arry[p2++];
        }
        while (p1 <= mid){
            help[i++] = arry[p1++];
        }
        while (p2 <= right){
            help[i++] = arry[p2++];
        }

        for (int j = 0; j < help.length; j++) {
            help[left + j]  =help[j];
        }
        return res;
    }

}
